1. Field of the Invention
The present invention relates generally to broadcast data encryption that uses encryption keys.
2. Description of the Related Art
Various broadcast encryption systems have been proposed for encrypting content that is broadcast to potentially millions of receivers using recorded media such as CDs and DVDs, or via wireless broadcast methods such as satellite broadcasts. These systems are intended to encrypt content such that only authorized receivers (also referred to as “users” and “player-recorders”) can decode and play the content, but software- or hardware-implemented pirate devices (also referred to as “clones” and “evil devices”) that somehow manage to obtain a valid decryption key from an authorized device (“traitor”) nonetheless cannot decrypt and play the content.
An example of such a system is disclosed in the present assignee's U.S. Pat. No. 6,118,873, incorporated herein by reference. As set forth therein, only authorized player-recorders can play and/or copy the content and only in accordance with rules established by the vendor of the content. In this way, pirated copies of content, which currently cost content providers billions of dollars each year, can be prevented.
Another example of a broadcast encryption system is the “Subset Cover” system disclosed in the present assignee's co-pending U.S. patent application Ser. No.  09/770,877, incorporated herein by reference. This latter system, details of which are set forth below for illustration, is directed to the difficult scenario of “stateless” receivers, i.e., receivers that do not necessarily update their encryption state between broadcasts to accept countermeasures against pirate devices. For example, a television that subscribes to a pay channel might have its set-top box deenergized for a period of time during which updated encryption data might be broadcast over the system. Such a device would be rendered “stateless” if it happens to be unable to update itself after being reenergized, and would not receive updates that would be necessary for future content decryption. Another example of a stateless receiver would be a player-recorder of CDs and DVDs, which ordinarily does not interact with other system components and which will not receive every possible piece of encryption data updates, since no player receives every vended disk.
As recognized by the present invention, decryption keys in broadcast encryption systems can become compromised, enabling unauthorized pirate devices to decrypt content. Such pirate devices can be implemented in hardware or in software, and in the latter case can be posted on the Internet for free downloading to anyone who wants to obtain proprietary content without paying for it. In any case, the present invention is directed to countering the propagation of pirate clones by either finding the identities of system receivers (“traitors”) whose keys have been obtained by the pirate, or to render pirate clones useless by finding an encryption that cannot be decrypted by the clones but that can be decrypted by authorized users.
The present invention is particularly (but not exclusively) focussed on the problem of tracing traitors in the Subset-Cover system. Unlike the system of the above-referenced '873 patent, in the Subset-Cover system no key overlap exists between devices. One result of key overlap is that in the patented '873 system, it is perfectly normal in operation that some device keys will correctly decrypt content and some will not, so that a clone cannot ascertain whether it is being tested simply by observing whether messages being sent to it cannot be decrypted with all its keys. This is not true in the Subset-Cover system, since every device has at least one unique key. Consequently, if a clone obtains keys from multiple traitors, and if one key from one traitor is properly decrypting content while another key from another traitor is not, the clone can deduce that it is under test.
Once a clone deduces it is under test, it can undertake any one of a number of countermeasures, such as switching identities between traitors, or even self-destructing. Of course, in the case of self-destruction the licensing agency can simply obtain another clone for further (modified) testing, but this takes time. With these critical observations in mind, the present invention has provided the below solutions to one or more of the observations.